package utils;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class EulerCycle {
    private int n;
    private List<Integer> path;
    
    @SuppressWarnings("unchecked")
    public EulerCycle(MinimumSpanningTree tree) {
        List<Integer>[] adjacencyList; 
        n = tree.getN();
        adjacencyList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++)
            adjacencyList[i] = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++)
            if (tree.getDad(i) != 0) {
                for (int j = 0; j < 2; j++) {
                    adjacencyList[i].add(tree.getDad(i));
                    adjacencyList[tree.getDad(i)].add(i);
                }
            }
        Stack<Integer> stack = new Stack<Integer>();
        path = new ArrayList<Integer>();
        stack.add(n);
        do {
            int top = stack.peek();
            if (adjacencyList[top].size() == 0) {
                path.add(top);
                stack.pop();                
            } else {
                stack.push(adjacencyList[top].get(0));
                int index, obj;
                obj = adjacencyList[top].get(0);
                adjacencyList[top].remove(0);
                index = 0;
                for (int j: adjacencyList[obj]) {
                    if (j == top)
                        break;
                    else
                        index++;
                }
                adjacencyList[obj].remove(index);
            }
        } while (!stack.isEmpty());
        System.out.println("Complete Euler !!!");
    }

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    public List<Integer> getPath() {
        return path;
    }

    public void setPath(List<Integer> path) {
        this.path = path;
    }
    
    public void displayEulerCycle() {
        for (int node:path) 
            System.out.print(node + " -> ");
        System.out.println();        
    }
}
